package com.pan.alg.basic.sortbasic;

import org.apache.commons.lang3.ArrayUtils;

/**
 * @author by panstark
 * @description
 * @notice
 * @date 2020/12/21
 */
public class  Insert2part {


    public static void insertSort2part(int[] arr){

        int length = arr.length;
        for(int i=0;i<length;i++){
            int temp = arr[i];
            int index = insert(arr,0,i,temp);
            moveleft(arr,index,i);
            arr[index]=temp;
            System.out.println("--第"+i+"次坐标为:"+index);
            System.out.println("--第"+i+"次循环:"+ArrayUtils.toString(arr));

        }
    }

    /**
     * i坐标之前的数列是有序的
     * @param arr
     * @param start
     * @param end
     * @param temp
     * @return
     */
    private static int insert(int[] arr, int start,int end,int temp) {

        if(end-start<=0||end==0){
            return end;
        }

        int part = (start+end)/2;
        if(arr[part]==temp){
            return part;
        }

        int index = 0;
        if(arr[part]>temp){
            index= insert(arr,start,part,temp);
        }else if(arr[part]<temp){
            index=insert(arr,part+1,end,temp);
        }
        return index;
    }

    private static void moveleft(int[] arr,int index, int end) {
        for(int i=end;i>index&&i>0;i--){
            arr[i]=arr[i-1];
        }
    }


    public static void main(String[] args) {
        int[] arr ={4,3,6,7,8,9,4,2,11,23,56,43,45};

        insertSort2part(arr);

        System.out.println(ArrayUtils.toString(arr));

    }
}
